package xio.leetcode.java;

import xio.leetcode.java.base.ListNode;

/**
 * LeetCode 21: Merge Two Sorted Lists
 *
 * 考察点：链表的基本操作
 * 递归的实现方法
 * l1: 2 -> 4 -> 9
 * l2: 1 -> 3 -> 5
 *
 * l1 和 l2 merge:
 * 2 > 1 :
 *   l2 > 1 ->
 *     2 -> 4 -> 9 和  3 -> 5 继续 merge:
 *     2 < 3 :
 *   2 ->
 *     4 -> 9 和 3 -> 5继续merge：
 *     4 > 3 :
 *   3 ->
 *     4 -> 9 和 5 继续merge：
 *     4 < 5:
 *   4 ->
 *      9 和 5 继续merge：
 *      9 < 5:
 *   5 ->
 *      有一链表为已为空，当前next就指向另一非空链表
 *   9
 *   返回l2
 */
public class LC21_MergeTwoSortedLists {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 != null && l2 != null){
            if (l1.val > l2.val){
                l2.next = mergeTwoLists(l1,l2.next);
                return l2;
            }else {
                l1.next = mergeTwoLists(l1.next,l2);
                return l1;
            }
        }else {
            return l1 == null? l2:l1;
        }
    }
}
